package 链表;

/**
 * 86. 分隔链表
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 思路： 可以使用辅助节点的方式，创建两个链表，分别保存小于x的节点和大于等于x的节点，最后再合并两个链表
 * 解题步骤：
 *  1：创建两个虚拟头节点：分别用于存储小于 x 的节点和大于或等于 x 的节点。
 *  2：遍历链表：遍历原链表，将节点根据值的大小分别连接到两个虚拟头节点对应的链表中。
 *  3：合并链表：将小于 x 的链表和大于或等于 x 的链表连接起来。
 *  4：返回结果：返回合并后的链表。
 */
public class L_86 {

    public ListNode partition(ListNode head, int x) {
        // 创建两个虚拟头节点
        ListNode lessHead = new ListNode(0); // 存储小于 x 的节点
        ListNode greaterHead = new ListNode(0); // 存储大于或等于 x 的节点
        ListNode less = lessHead; // 指向小于 x 的链表的当前节点
        ListNode greater = greaterHead; // 指向大于或等于 x 的链表的当前节点

        // 遍历原链表，将节点根据值的大小分别连接到两个虚拟头节点对应的链表中
        while (head != null){
            if(head.val < x){
                // 添加到值小于x的链表之中
                less.next = head;
                less = less.next;
            }else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        // 然后合并
        greater.next = null; // 将greater链表断开，防止成环
        // 连接 less 链表和 greater 链表
        less.next = greaterHead.next;
        return lessHead.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
